package leetcode_801_900;

import common.SegmentTree;

import java.util.*;

public class LeeCode_828 {
    public static void main(String[] args) {
        System.out.println(uniqueLetterString2("ABC"));
        System.out.println(uniqueLetterString2("AA"));
        System.out.println(uniqueLetterString2("ABA"));
        System.out.println(uniqueLetterString2("LEETCODE"));
    }
    private static int uniqueLetterString2(String s) {
        int n = s.length();
        Map<Character, List<Integer>> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            char c = s.charAt(i);
            if (map.containsKey(c)){
                map.get(c).add(i);
            }else {
                List<Integer> list = new ArrayList<>();
                list.add(i);
                map.put(c, list);
            }
        }
        int ans = 0;
        for (Character key : map.keySet()) {
            List<Integer> son = map.get(key);
            int m = son.size();
            ans += (son.get(0) + 1) * ((m > 1 ? son.get(1) : n) - son.get(0));
            for (int i = 1; i < m - 1; i++) {
                ans += (son.get(i) - son.get(i - 1)) * (son.get(i + 1) - son.get(i));
            }
            if(m > 1){
                ans += (n - son.get(m - 1)) * (son.get(m - 1) - son.get(m - 2));
            }
        }
        return ans;
    }
    private static int uniqueLetterString(String s) {
        int n = s.length(), ans = 0;
        int[][][] dp = new int[n + 1][26][2];
        for (int i = 1; i <= n; i++) {
            int now = s.charAt(i - 1) - 'A';
            for (int j = 0; j < 26; j++) {
                if (now == j){
                    int pre = dp[i - 1][j][1];
                    dp[i][j][0] = i - pre;
                    ans += dp[i][j][0];
                    dp[i][j][1] = i;
                }else {
                    dp[i][j][0] = dp[i - 1][j][0];
                    dp[i][j][1] = dp[i - 1][j][1];
                    ans += dp[i][j][0];
                }
            }
        }
        return ans;
    }
}
